package bishiqiangxun;

import java.util.*;


          class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        //用优先级队列  每次都可以比较k个元素
        PriorityQueue<ListNode> queue = new PriorityQueue<>((val1,val2) -> val1.val - val2.val);
        for(int i = 0; i < lists.size();i++) {
            if(lists.get(i) != null) {
                queue.add(lists.get(i));
            }
        }
        ListNode ret = new ListNode(0);  //加一个表头
        ListNode head = ret;

        while(!queue.isEmpty()) {
            //只要不为空就可以
            ListNode tmp = queue.poll();
            // System.out.println(tmp);
            head.next = tmp;
            head =head.next;
            if(tmp.next != null) {
                //加进队列
                queue.add(tmp.next);
            }

        }

        return ret.next;

    }
}
